package com.example.javademo.util;

/**
 * @Description :
 * @Author 北风
 * @Date Created in 2021/10/8 10:55
 */
public class KMP {
    public static void main(String[] args) {

        String str1 = "ababcaaababababcababaaaab";
        String str2 = "aaaaab";
        System.out.println(str1.indexOf(str2));

        int m = str1.length(), n = str2.length();
        int[] next = new int[n];
        next[0] = -1;
        int index = 0, pre = -1;
        while (index < n - 1) {
            if (pre == -1 || str2.charAt(index) == str2.charAt(pre)) {
                next[++index] = ++pre;
            } else {
                pre = next[pre];
            }
        }

        int i = 0, j = 0;
        while (i < m && j < n) {
            if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
                i ++;
                j ++;
            } else {
                j = next[j];
            }
        }

        System.out.println(j == n ? i - j : -1);
    }
}
